
public class redblacktree {
    public static void main(String[] args) {
        RB_BST<Integer,Integer>a=new RB_BST();
        a.put(10, 8);
        a.put(7, 5);
        a.put(12, 6);
        System.out.println(a.get(12));
    }
    
}




class RB_BST<KEY extends Comparable<KEY>,VALUE>
{
    private Node root;
    private static final boolean RED=true;
    private static final boolean BLACK=false;
    private class Node
    {
        KEY key;
        VALUE value;
        Node left,right;
        int N;
        boolean color;
        Node(KEY key,VALUE value,int N,boolean color)
        {
            this.key=key;this.value=value;this.N=N;this.color=color;
        }
    }
    private boolean isRed(Node x)
    {
        if(x==null)return false;
        return x.color==RED;
    }
    Node rotateLeft(Node h)
    {
        Node x=h.right;
        h.right=x.left;
        x.left=h;
        x.color=h.color;
        h.color=RED;
        x.N=h.N;
        h.N=1+size(h.left)+size(h.right);
        return x;
    }
    Node rotateRight(Node h)
    {
        Node x=h.left;
        h.left=x.right;
        x.right=h;
        x.color=h.color;
        h.color=RED;
        x.N=h.N;
        h.N=1+size(h.left)+size(h.right);
        return x;
    }
    void flipColors(Node h)//颜色转换
    {
        h.color=RED;
        h.left.color=BLACK;
        h.right.color=BLACK;
    }
    public void put(KEY key,VALUE value)
    {
        root=put(root,key,value);
        root.color=BLACK;
    }
    private Node put(Node h,KEY key,VALUE value)
    {
        if(h==null)return new Node(key,value,1,RED);
        int cmp=key.compareTo(h.key);
        if(cmp<0)h.left=put(h.left,key,value);
        else if(cmp>0)h.right=put(h.right,key,value);
        else h.value=value;
        if(isRed(h.right) && !isRed(h.left))h=rotateLeft(h);
        if(isRed(h.left) && isRed(h.left.left))h=rotateRight(h);
        if(isRed(h.left) && isRed(h.right))flipColors(h);
        h.N=1+size(h.left)+size(h.right);
        return h;
    }
    //==================其他===================
    public int size(){return size(root);}
    private int size(Node x)
    {
        if(x==null)return 0;
        return x.N;
    }
    public VALUE get(KEY key){return get(root,key);}
    private VALUE get(Node x,KEY key)
    {
        if(x==null)return null;
        int cmp=key.compareTo(x.key);
        if(cmp<0)return get(x.left,key);
        else if(cmp>0)return get(x.right,key);
        else return x.value;
    }
}